1. Field of the Invention
This invention relates to systems and methods for transmission of still images over relatively low-speed communication channels. More specifically the invention relates to progressive image streaming over low speed communication lines, and may be applied to a variety of fields and disciplines, including commercial printing and medical imaging, among others.
2. Brief Description of the Prior Art
In a narrow bandwidth environment, a simple transfer to the client computer of any original image stored in the server's storage is obviously time consuming. In many cases the user only wishes to view a low resolution version of the image and perhaps several high-resolution details, in these instances it would be inefficient to transfer the full image. This problem can be overcome by storing images in a compressed format. Examples of such formats include standards such as Progressive JPEG (W. Pennebaker and J. Mitchel, “JPEG, still image data compression standard”, VNR, 1993) or the upcoming JPEG2000 (D. Taubman, “High performance scalable image compression with EBCOT”, preprint, 1999). These formats allow progressive transmission of an image such that the quality of the image displayed at the client computer improves during the transmission.
In some applications such as medical imaging, it is also necessary that whenever the user at the client computer is viewing a portion of the highest resolution of the image, the progressive streaming will terminate at lossless quality. This means that at the end of progressive transmission the pixels rendered on the screen are exactly the pixels of the original image. The current known “state-of-the-art” wavelet algorithms for progressive lossless streaming all have a major drawback: their rate-distortion behavior is inferior to the “lossy” algorithms. The implications of this include:
1. Whenever the user is viewing any low resolution version of the image (at low resolutions the term “lossless” is not well defined) more data needs to be sent for the same visual quality.
2. During the progressive transmission of the highest resolution, before lossless quality is achieved, more data needs to be sent for the same visual quality.
Researchers working in this field are troubled by these phenomena. F. Sheng, A. Bilgin, J. Sementilli and M. W. Marcellin state in “Lossy to Lossless Image Compression Using Reversible Integer Wavelet Transform”, Proc. IEEE International Conf. On Image Processing, 1998: “. . . Improved lossy performance when using integer transforms is a pursuit of our on-going work.” An example is provided below in Table 1.
TABLE 1Comparison of the lossy compression performances(implemented by the (7, 9) Wavelet) to a lossless compression(implemented by a reversible (4, 4) Wavelet) of “Barabara”image(PSNR (dB)) ([SBSM]).Rate (bit per pixel)Wavelet0.10.20.50.71.0Floating Point 7 × 924.1826.6531.6434.1736.90Reversible (4, 4)23.8926.4131.1433.3535.65
As can be seen from Table 1, state of the art progressive lossless coding is inferior to lossy coding by more than 1 dB at high bit-rates.
Indeed, intuitively, the requirement for lossless progressive image transmission should not effect the rendering of lower resolutions or the progressive “lossy” rendering of the highest resolution before lossless quality is obtained. The final lossless quality should be a layer that in some sense is added to a lossy algorithm with minor (if any) effect on its performance.
The main problem with known lossless wavelet algorithms, such as Set Partitioning in Hierarchical Trees (SPIHT) A. Said and W. Pearlman, “A new, fast and efficient image codec based on set partitioning”, IEEE Trans. Circuits and Systems for Video Tech. 6 (1996), 243–250 and compression with reversible embedded wavelets (CREW) A. Zandi, J. D. Allen, E. L. Schwartz and M. Boliek, “CREW: Compression with reversible embedded wavelets”, Proc. of Data Compression Conference (Snowbird, Utah), 212–221, 1995, is that they use special “Integer To Integer” transforms (see “Wavelet transforms that map integers to integers”, A. Calderbank, I. Daubechies, W. Sweldens, B. L. Yeo, J. Fourier Anal. Appl., 1998). These transforms mimic “mathematically proven” transforms that work well in lossy compression using floating-point arithmetic implementations. Because they are constrained to be lossless, they do not approximate their related floating-point algorithms sufficiently well. Although in all previous work there have been attempts to correct this approximation in the progressive coding stage of the algorithm, the bad starting point, an inefficient transform, prevented previous authors from obtaining acceptable rate-distortion behavior.
The system and method of the present invention solves the rate-distortion behavior problem. Using the fact that images are two-dimensional signals, novel 2D lossless Wavelet transforms are disclosed that better approximate their lossy counterparts. As an immediate consequence the lossless progressive coding algorithm of the present invention has the same rate-distortion of a lossy algorithm during the lossy part of the progressive transmission.